package 哈希表;

import java.util.HashMap;
import java.util.Map;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/16 10:13
 */
public class leetcode560和为k的子数组 {

    /*
     顺便 ，顺着这个题，理解一下，离散化思想！
     这里如果使用 数组[] 来 替代 map 的话, 那么下标 i 就是  nums[i] , map[i] 就是 i (或者说是 nums[i]) 出现的次数
     但是这有 一些问题:
     ① 如果 nums[i] 的 值域 非常 大 ,那么 这个 map数组的 大小 就非常的大,
     eg : nums[i] ∈ [1 , 10 ^ 9], 明显需要离散化 (需要 Map 来离散化)
     ②:
     如果nums[i] 就像 该题 一样可以 取 负值 的话, 下标 没法 < 0
     这也是一问题
     */

    /*
    相当于 是两数之和的 进阶版!
     这个题, 如果能够理解透彻的话,需要经常的 去理解一下!
     还是有点抽象的!
     确实 抽象!
     */

    /*
     看到 子数组和 sum, 想一下 能不能前缀和呢
     要有这样的一个敏感性!
     nums[i] 有正数, 有负数!
     */
    public int solution(int nums[],int k){
        int preSum[] = new int[nums.length + 1];
        // preSum[i]  [0, i) 的区间和(左闭右开)
        for(int i = 0;i < nums.length;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }

        Map<Integer,Integer> map = new HashMap<>();
        /*
         这是一个 非常不好理解的地方, 在纸上比划一下,理解一下,就明白了!
         这里 可能 会绕进去, 进行一些说明:
         1. 从 preSum[i] - k 入手, 如果  preSum[i] - k = 0, 则说明 preSum[i] = k, [0, i)  就是 满足 的子数组
         2. 如果 preSum[i] - k != 0 ;  判断 一下 preSum[j] = preSum[i] - k
         如果 map 中 preSum[j] 的个数 > 0 , 则说明 前缀和 为 preSum[j] 的 子数组存在, 则说明 子数组 k 也存在!
         这里 可能有点绕, 下次看到的时候, 直接从这里去理解 就行了!
         */
        map.put(0,1);
        int count = 0;
        /*
         下面只用到了 preSum[i], 这样的话,其实都不用前缀和数组都可以的!
         */
        for(int i = 1;i <= nums.length;i++){
            count += map.getOrDefault(preSum[i] - k,0);
            map.put(preSum[i],map.getOrDefault(preSum[i],0) + 1);
        }
        return count;
    }

    /*
     不使用前缀和数组, 直接 使用一个 变量sum 即可

     - 解释下原理:
     遍历 数组nums , 枚举  i, 求出 [0 , i] 区间内. 以 i 为 **末端点**  的子数组和 为 k 的个数, 也就是 下面这句话

     -  而求某个点为终点且和为k的子数组是经典的枚举终点+哈希表习题了

     map.put(0,1) 这是 初始的条件, 因为 preSum[i + 1] == k 那 [0,i] 本身,就是满足要求的子数组
     */

    public int function(int nums[],int k){
        int sum = 0, ans = 0;
        Map<Integer,Integer> map = new HashMap<>(nums.length);

        map.put(0,1); // 这个很关键
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
            ans += map.getOrDefault(sum - k,0);
            map.put(sum, map.getOrDefault(sum,0) + 1);
        }
        return ans;
    }





    // 暴力 N ^ 2
    public int voilent(int nums[],int k){
        int preSum[] = new int[nums.length + 1], ans = 0;
        for(int i = 0;i < nums.length ;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
        for(int i = 0;i < nums.length ;i++){
            for(int j = i;j < nums.length ;j++){
                if(preSum[j + 1] - preSum[i] == k){
                    ans++;
                }
            }
        }
        return ans;
    }

    /*
        //举个例子:
        int[] a = {1, 2, 3, 4, 5, 6};

        //将每个元素累加,对应下面这个数组:
        int[] b = {1, 3, 6, 10, 15, 21};

        //因为题干要求是连续子数组,所以任意的b[i]与b[j]的差值即为子数组的和.
        //所以就变成了找出b[i]与b[j]的差等于k,有多少种组合方式.

        //第一题是找两数之和a+b=target，这题是找两数之差a-b=target

        //因为是求有多少种组合，所以key是元素，value是次数，次数初始化全是1
     */

    /*
      上面的 思路 完全转换成 两数 之和 的变种， 两数 之差
      a - b = k
      再从 左向右 枚举的过程中， a ， k 是定值， 只需要用hash 表 缓存  已经遍历的过的 元素就行了
      但是有个 特殊的点 ， 就是 a 本身 可能是 等于 k 的 所以 再遍历的过程中， 首先判断下 a ==k 直接 +1
      还是 那句话： **遍历 固定的 值， 去找不确定的值**
     */
    public int subarraySum(int[] nums, int k) {
        int ans = 0,sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
            if(sum == k){
                ans++;
            }
            if(map.containsKey(sum - k)){
                ans += map.get(sum - k);
            }
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return ans;
    }

}
